package com.liunian.test;

public class RepeatedSubstringPattern459 {

	/**
	 给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

	 示例 1:
	 输入: s = "abab"
	 输出: true
	 解释: 可由子串 "ab" 重复两次构成。

	 示例 2:
	 输入: s = "aba"
	 输出: false

	 示例 3:
	 输入: s = "abcabcabcabc"
	 输出: true
	 解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)
	 */
	public boolean repeatedSubstringPattern(String s) {
		int n = s.length();
		char[] chars = s.toCharArray();
		int[] next = getNext(chars, n);
		if (n - next[n - 1] != 0 && n - next[n - 1] <= next[n - 1] && n % (n - next[n - 1]) == 0) {
			return true;
		}
		return false;
	}

	private int[] getNext(char[] chars, int n) {
		int[] next = new int[n];
		int j = 0;
		for (int i = 1; i < n; i++) {
			while (j > 0 && chars[i] != chars[j]) {
				j = next[j - 1];
			}
			if (chars[i] == chars[j]) {
				j++;
			}
			next[i] = j;
		}
		return next;
	}

	public static void main(String[] args) {
		RepeatedSubstringPattern459 pattern = new RepeatedSubstringPattern459();
		pattern.repeatedSubstringPattern("abab");
	}

}
